package dp;

/**
 * @author wcj
 * @Date 2021/7/6 17:11
 * @Version 1.0
 */
public class MaxSymmetrySeq {

    /**
     * 最长回文子序列
     * 动态规划：
     * ①状态定义：dp[i][j]表示第i个字符到第j个字符的最长回文子序列的长度
     * ②状态转移方程：
     * i==j,dp[i][j]=1
     * j-i==1,如果s.charAt(i)==s.charAt(j),dp[i][j]=2
     * 如果s.charAt(i) == s.charAt(j),dp[i][j] = dp[i+1][j-1]+2,j-i>=2
     * 否则，dp[i][j] = dp[i][j-1]
     * ③状态初始化
     *
     * @param s
     * @return
     */
    public static int maxSymmetrySeq(String s) {
        int[][] dp = new int[s.length()][s.length()];
        for (int i = s.length() - 1; i >= 0; i--) {
            for (int j = i; j < s.length(); j++) {
                if (i == j) {
                    dp[i][j] = 1;
                } else if (j - i == 1) {
                    dp[i][j] = s.charAt(i) == s.charAt(j) ? 2 : 1;
                } else {
                    if (s.charAt(i) == s.charAt(j)) {
                        dp[i][j] = dp[i + 1][j - 1] + 2;
                    } else {
                        dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                    }
                }
            }
        }
        return dp[0][s.length() - 1];
    }
}
